public class Solution1269 {
    public int numWays(int steps, int arrLen) {
        int[] lastDp=new int[arrLen];
        lastDp[0]=1;
        int maxLen=Math.min(arrLen,steps+1);
        for (int i = 1; i <= steps ; i++) {
            int[] tmpDp=new int[arrLen];
            for (int j = 0; j < maxLen; j++) {
                int tmpRes=0;
                tmpRes=(tmpRes+lastDp[j])%1000000007;
                tmpRes=(tmpRes+(j-1>=0? lastDp[j-1]:0))%1000000007;
                tmpRes=(tmpRes+(j+1<arrLen? lastDp[j+1]:0))%1000000007;
                tmpDp[j]=tmpRes;
            }
            lastDp=tmpDp;
        }
        return lastDp[0];
    }

    public static void main(String[] args) {
        Solution1269 s=new Solution1269();
        System.out.println(s.numWays(27,
                7));
    }
}
